package com.ma;

import static com.ma.sort.marge;

public class mergeTest {

    /**
     * 如果递归满足T(N)=a*T(N/b)+O(N^d)
     * 1) log(b,a)>d O(N^log(b,a))
     * 2) log(b,a)<d O(N^d)
     * 3) log(b,a)=d O(N^d*logN)
     *
     *
     * 归并排序相较于冒泡、选择、插入排序
     * 归并并没有浪费比较行为每一次比较都使划分两组分别有序
     * 但冒泡、选择、插入没做到比较就变有序,要不就是到某一阶段才开始有序或者有序的部分在逐步扩大
     * 就是说会有无意义的移动行为在执行
     * 所以归并优于另外三个
     * O(n*logN)>O(N^2)
     */



    /**
     * 归并递归测试
     * T(N)=2*T(N/2)+O(N^1)
     * O(N*logN)
     */
    public void mergeRecursionTest(){

    }
    public static void recursion(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        process(arr,0,arr.length-1);
    }
    public static void process(int[] arr,int L,int R){
        if(L==R){
            return;
        }
        int mid=L+((L-R)>>1);
        process(arr, L, mid);
        process(arr, mid+1, R);
        marge(arr,L,mid,R);
    }

    /**
     * 归并非递归测试
     * mS=1   O(n)
     * mS=2   O(n)
     * mS=4   O(n)
     *  .
     *  .
     *  .
     * 共log(2,n)次
     * O(N*logN)
     */
    public void margeNoRecursionTest(){

    }
    public static void NoRecursion(int[] arr){
        if(arr==null||arr.length<2){
            return;
        }
        int N=arr.length;
        int margeSize=1;//左组长度，即单位组长度
        //在不越界的前提下循环
        while (margeSize<N){

            int L=0;//左组起始位置
            while (L<N){
                int M=L+margeSize-1;//左组边界
                if(M>=N){
                    //如果左组越界结束
                    break;
                }
                int R=Math.min(M+margeSize,N-1);//右组起始位置
                marge(arr,L,M,R);//将左右两组做归并
                L=R+1;//来到下一个两组
            }
            if(margeSize>N/2){
                //当单位组长度大于N/2时结束
                //这时证明单位组长度已经将他分为一个左右组且右组小于等于单位组，且执行完归并排序则称排序结束
                break;
            }
            margeSize<<=1;//呈二倍增加
        }
    }


}
